A 3-path vertex cover in a graph is a vertex subset $C$ such that every pathof three vertices contains at least one vertex from $C$. The parameterized3-path vertex cover problem asks whether a graph has a 3-path vertex cover ofsize at most $k$. In this paper, we give a kernel of $5k$ vertices and an$O^*(1.7485^k)$-time and polynomial-space algorithm for this problem, both newresults improve previous known bounds.
展开▼
机译：图中的3路径顶点覆盖是一个顶点子集$ C $，使得三个顶点的每个路径都包含至少一个来自$ C $的顶点。参数化的3路径顶点覆盖问题询问图是否具有大小最大为$ k $的3路径顶点覆盖。在本文中，我们给出了一个$ 5k $顶点的核以及一个$ O ^ *（1.7485 ^ k）$-time和多项式空间算法，这两个新结果都改善了以前的已知范围。
展开▼
